package code.DP.斐波那契数列;

import java.util.HashMap;

public class Solution {
	HashMap<Integer, Integer> f2Map = new HashMap<>();

	public static void main(String[] args) {
		System.out.println(10 >> 1);
		System.out.println(10 & 1);

		int[][] m1 = new int[4][3];
		m1[0] = new int[]{5, 2, 4};
		m1[1] = new int[]{3, 8, 2};
		m1[2] = new int[]{6, 0, 4};
		m1[3] = new int[]{0, 1, 6};

		int[][] m2 = new int[3][2];
		m2[0] = new int[]{2, 4};
		m2[1] = new int[]{1, 3};
		m2[2] = new int[]{3, 2};

		int[][] ints = muliMatrix(m1, m2);
		System.out.println(ints);

		int[][] ints1 = matrixPower(new int[][]{{2, 0}, {0, 2}}, 10);
		System.out.println(ints);

		Solution solution = new Solution();
		int f3 = solution.f3(10);
		System.out.println(f3);
		int f1 = solution.f1(10);
		System.out.println(f1);
		int f2 = solution.f2(55);
		System.out.println(f2);
		int f4 = solution.f4(55);
		System.out.println(f4);
	}

	public int f1(int n) {
		if (n < 1) {//1、1、2、3、5、8、13、21、34 如果传入的n比1小，不用计算。
			return 0;
		}
		if (n <= 2) {//2. base case： n=1，n=2 的时候返回 1
			return 1;
		}
		return f1(n - 1) + f1(n - 2);//1.将公式代入递归结构
	}

	public int f2(int n) {
		if (n < 1) {
			return 0;
		}
		if (n <= 2) {
			return 1;
		}
		if (f2Map.containsKey(n)) {//1.如果备忘录已经存在某个n的结果，直接使用就行了。
			return f2Map.get(n);
		}
		int res = f2(n - 1) + f2(n - 2);
		f2Map.put(n, res);//将当前n的结果记录到备忘录。
		return res;
	}

	public int f3(int n) {
		if (n < 1) {
			return 0;
		}
		if (n <= 2) {
			return 1;
		}
		int now = 2;//1.记录第三个位置的结果。
		int pre = 1;//2.记录上一个位置的结果。
		for (int i = 3; i < n; i++) {//3.从第四个位置开始累加。
			int tmp = now; //5.记录计算前的结果，当做新的上一个值
			now = now + pre;//4.当前+之前 = 新的结果
			pre = tmp;//6.修改上一个值。
		}
		return now;
	}

	public int f4(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return 1;
		}
		int[][] base = {{1, 1}, {1, 0}};//1.推到出来的基础情况矩阵
		int[][] res = matrixPower(base, n - 2);//2.计算矩阵的n-2次方，n<=2的时候已经直接返回了。
		return res[0][0] + res[1][0];// 3. 根据公式可以知道 res[0][0]=f(n-1) res[1][0]=f(n-2)
	}

	public static int[][] matrixPower(int[][] m, int p) {
		if (m == null || m.length == 0) {//0.直接返回
			return null;
		}
		int[][] res = new int[m.length][m[0].length];//1.创建一个单位矩阵，与某个矩阵x相乘之后保证x保持不变。
		for (int i = 0; i < res.length; i++) {
			res[i][i] = 1;
		}
		int[][] tmp = m;
		for (; p != 0; p >>= 1) {//2.每次都将p右移一个位置，比如二进制 1010>>101>10>1>0 即 10>5>2>1>0
			if ((p & 1) != 0) {//3.判断是不是奇数，奇数的情况特殊,没办法直接做矩阵平方的运算，将它乘以单位矩阵保存下来。
				res = muliMatrix(res, tmp);//5.比如在5的时候 tmp * tmp^4，如果不将左侧的tmp记录下来那么结果就错了。
			}
			tmp = muliMatrix(tmp, tmp);//4.矩阵平方。
		}
		return res;
	}

	public static int[][] muliMatrix(int[][] m1, int[][] m2) {
		//1.矩阵乘法，要求m1的行等于m2的列。
		if (m1 == null || m2 == null || m1.length == 0 || m2.length == 0 || m1.length != m2[0].length) {
			return null;
		}
		int col = m1.length;//2.结果矩阵的行数等于m1的行数。
		int row = m2[0].length;//3.结果矩阵的列数等于m2的列数。
		int[][] res = new int[col][row];//4.根据行列创建一个结果矩阵
		//5.将计算结果存入结果矩阵，用两层for循环的遍历结果矩阵的每一个格子
		for (int i = 0; i < col; i++) {
			for (int j = 0; j < row; j++) {
				for (int k = 0; k < m2.length; k++) {//将m1这一行的数分别乘以m2这一列的数,其中m2.length控制相层的个数。
					res[i][j] += m1[i][k] * m2[k][j];
				}
			}
		}
		return res;
	}
}
